#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>

template <typename Iter>
void quick_sort(Iter begin, Iter end)
{
    if (std::distance(begin, end) <= 1)
        return;
    auto pivot = *begin;

    Iter middle = std::partition(std::next(begin), end,
        [pivot](const auto& value) {
            return value > pivot;
        });

    // std::prev(middle)属于前半部分，
    // 与begin交换后，整个数组以std::prev(middle)为界，
    // std::prev(middle)作为前半部分的结尾，且不需要参与排序了
    std::iter_swap(begin, std::prev(middle));

    quick_sort(begin, std::prev(middle));
    quick_sort(middle, end);
}

template <typename Iter, typename Func>
void quick_select_nth(Iter begin, Iter end, Func f, int number)
{
    if (std::distance(begin, end) <= 1)
        return;

    auto pivot = *begin;
    Iter middle = std::partition(std::next(begin), end,
        [pivot, &f](const auto& value) {
            return f(value, pivot);
        });

    std::iter_swap(begin, std::prev(middle));

    if (std::distance(begin, std::prev(middle)) >= number) {
        quick_select_nth(begin, std::prev(middle), f, number);
    } else {
        number -= std::distance(begin, std::prev(middle));
        quick_select_nth(middle, end, f, number);
    }
}

int main()
{
    std::vector<int> data { 21, 5, 7, 89, 35, 10, 2, 99 };
    // std::vector<int> data { 1, 1, 1, 1, 1 };
    // quick_sort(data.begin(), data.end());

    for (auto x : data)
        std::cout << x << " ";
    std::cout << std::endl;

    int number = 3;
    quick_select_nth(data.begin(), data.end(), std::less<>(), number);
    for (int i = 0; i < 3; ++i) {
        std::cout << data[i] << " ";
    }
    std::cout << std::endl;
}
